package com.leaves.leetcode.array.t454_4SumⅡ;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;


/**
 * 核心要点：
 *分组 + 哈希表
 * 1、通过哈希表缓存嵌套循环中一部分嵌套的结果，将高时间复杂度的重复计算抽出来计算，把结果放到Map中，减少最内层嵌套循环的时间复杂度
**/
 class Solution {
    /**
     * 分组 + 哈希表
     * 1、通过哈希表缓存嵌套循环中一部分嵌套的结果，将高时间复杂度的重复计算抽出来计算，把结果放到Map中，减少最内层嵌套循环的时间复杂度
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(n)
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                map.put(nums1[i] + nums2[j], map.getOrDefault(nums1[i] + nums2[j], 0) + 1);
            }
        }

        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                res += map.getOrDefault(-nums3[i] - nums4[j], 0);
            }
        }
        return res;
    }
 }